\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage{amsmath}
\usepackage{ctex}
\usepackage{listings}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{graphicx}

\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\begin{document}
% =================================================
\title{Report \# 2}

\author{徐翊钧 3220101901
  \thanks{Electronic address: \texttt{3220101901@zju.deu.cn}}}
\affil{(强基2201), Zhejiang University }


\maketitle

%\begin{abstract}
%   The abstract is not necessary for the theoretical homework, 
%  but for the programming project, 
% you are encouraged to write one.      

%\end{abstract}





% ============================================
\section*{NewtonInterpolation的设计.}

\subsection*{1.主要功能.}
NewtonInterpolation 类是一个专门用于执行牛顿插值的类。它没有继承任何其他类，也不被其他类继承。这个类的主要功能是使用给定的数据点（x 和 y 值）来构造一个插值多项式，并使用这个多项式来计算任意点 z 的插值。

\subsection*{2.重要成员函数.}
\begin{itemize}
    \item \textbf{构造函数} $\text{NewtonInterpolation}(\text{const std::vector<double>}\& x, \text{const std::vector<double>}\& y)$
    \begin{itemize}
        \item \textbf{接口：} 接收两个 $\text{std::vector<double>}$ 类型的参数，分别代表数据点的 $x$ 和 $y$ 值。
        \item \textbf{形参意义：}
            \begin{itemize}
                \item $\text{const std::vector<double>}\& x$：数据点的 $x$ 值。
                \item $\text{const std::vector<double>}\& y$：数据点的 $y$ 值。
            \end{itemize}
        \item \textbf{功能：} 检查 $x$ 和 $y$ 的大小是否相等，如果不等则抛出异常。计算插值多项式的系数并存储在 $\text{coef\_}$ 中。
    \end{itemize}
    
    \item \textbf{插值函数} $\text{double interpolate}(\text{double} z) \text{ const}$
    \begin{itemize}
        \item \textbf{接口：} 接收一个 $\text{double}$ 类型的参数 $z$。
        \item \textbf{形参意义：}
            \begin{itemize}
                \item $\text{double} z$：需要计算插值的点。
            \end{itemize}
        \item \textbf{功能：} 使用存储的插值多项式系数和 $x$ 值，计算并返回点 $z$ 处的插值结果。
    \end{itemize}
\end{itemize}

\subsection*{3.算法.}
利用构建差商表的思路计算牛顿插值的系数向量
%% \begin{lstlisting}[language=C++, caption={计算多项式系数}, label={lst:example}]  
%% function NewtonInterpolation(x, y)  
%%     if size(x) $\neq$ size(y) then  
%%         throw exception: "x and y must have the same size"  
%%     n $\gets$ size(x)  
%%     resize(coef\_, n)  
%%     resize(x\_, n)  
      
%%     for i $\gets$ 0 to n-1 do  
%%         coef\_[i] $\gets$ y[i]  
%%         x\_[i] $\gets$ x[i]  
      
%%     for level $\gets$ 1 to n-1 do  
%%         for i $\gets$ n-1 to level do  
%%             coef\_[i] $\gets$ (coef\_[i] - coef\_[i-1]) / (x\_[i] - x\_[i-level])  
%% \end{lstlisting} 
\begin{algorithm}[H]  
\caption{计算多项式系数}  
\label{lst:example}  
\begin{algorithmic}  
\Function{NewtonInterpolation}{$x, y$}  
    \If{$\text{size}(x) \neq \text{size}(y)$}  
        \State \textbf{throw} exception: "x and y must have the same size"  
    \EndIf  
    \State $n \gets \text{size}(x)$  
    \State \textbf{resize}($\text{coef\_}, n$)  
    \State \textbf{resize}($x\_, n$)  
      
    \For{$i \gets 0$ \textbf{to} $n-1$}  
        \State $\text{coef\_}[i] \gets y[i]$  
        \State $x\_[i] \gets x[i]$  
    \EndFor  
      
    \For{$\text{level} \gets 1$ \textbf{to} $n-1$}  
        \For{$i \gets n-1$ \textbf{to} $\text{level}$}  
            \State $\text{coef\_}[i] \gets (\text{coef\_}[i] - \text{coef\_}[i-1]) / (x\_[i] - x\_[i-\text{level}])$  
        \EndFor  
    \EndFor  
\EndFunction  
\end{algorithmic}  
\end{algorithm}  

然后利用秦九韶方法计算差值多项式的值。
%% \begin{listing}[H]
%% \caption{Interpolate using Newton's Interpolation Polynomial}
%% \begin{lstlisting}[language=C++]
%% def interpolate(z):
%%     n = len(coef_)
%%     result = coef_[n-1]
    
%%     for i in range(n-2, -1, -1):
%%         result = result * (z - x_[i]) + coef_[i]
    
%%     return result
%% \end{lstlisting}
%% \end{listing}
\begin{algorithm}[H]  
\caption{Interpolate using Newton's Interpolation Polynomial}  
\begin{algorithmic}  
\Function{interpolate}{$z$}  
    \State $n \gets \text{len}(\text{coef\_})$  
    \State $result \gets \text{coef\_}[n-1]$  
      
    \For{$i$ \textbf{from} $n-2$ \textbf{down to} $0$}  
        \State $result \gets result \times (z - x\_[i]) + \text{coef\_}[i]$  
    \EndFor  
      
    \State \Return $result$  
\EndFunction  
\end{algorithmic}  
\end{algorithm}  

% =========================================
\section*{HermiteInterpolation的设计.}

\subsection*{1.类的结构和功能}
HermiteInterpolation 类是一个专门用于执行 Hermite 插值的类。Hermite 插值是一种在给定数据点及其导数的情况下，构造一个多项式来逼近函数的方法。这个类没有继承任何其他类，也不被其他类继承。

该类的主要功能包括:
\begin{itemize}
    \item 使用提供的 x 值、y 值和对应的导数值来构造 Hermite 插值多项式。
    \item 计算任意给定点的插值结果。
\end{itemize}

\subsection*{2.重要成员函数}
\begin{itemize}
    \item 成员变量
    \begin{itemize}
        \item std::vector<double> coef：存储插值多项式的系数。
        \item std::vector<double> x：存储原始的 x 值，这些值用于计算插值多项式的系数，并在插值函数中用于计算多项式的值。
        \item std::vector<double> y：存储原始的 y 值，这些值是插值点的数据。
        \item std::vector<double> dy：存储原始的导数值，这些值是插值点的导数数据。
    \end{itemize}
    \item 成员函数
    \begin{itemize}
        \item 构造函数 $HermiteInterpolation(const std::vector<double>\& x_, const std::vector<double>\& y_, const std::vector<double>\& dy_)$
        \begin{itemize}
            \item 接口：接收三个 std::vector<double> 类型的参数，分别代表数据点的 x 值、y 值和对应的导数值。
            \item 形参意义：
            \begin{itemize}
                \item $const std::vector<double>\& x\_：$数据点的 x 值。
                \item $const std::vector<double>\& y\_：$数据点的 y 值。
                \item $const std::vector<double>\& dy\_：$数据点的导数值。
            \end{itemize}
            \item 功能：检查 x、y 和 dy 的大小是否相等，如果不等则抛出异常。计算 Hermite 插值多项式的系数并存储在 coef 中。
        \end{itemize}
        \item 插值函数 double interpolate(double z) const
        \begin{itemize}
            \item 接口：接收一个 double 类型的参数 z。
            \item 形参意义：double z：需要计算插值的点。
            \item 功能：使用存储的 Hermite 插值多项式系数和 x 值，计算并返回点 z 处的插值结果。
        \end{itemize}
    \end{itemize}
\end{itemize}

\subsection*{3.主要算法流程}
仍然是按照计算差商表方式来计算多项式系数

仍然是用秦九韶方法计算，减少数值误差

%% function interpolate(z):
%%     n = size(coef) / 2
%%     result = coef[2n-1]
%%     for i from 2n-2 down to 0:
%%         result = result * (z - x[i/2]) + coef[i]
%%     return result

\begin{algorithm}[H]  
\caption{Interpolation Function}  
\begin{algorithmic}  
\Function{interpolate}{$z$}  
    \State $n \gets \text{size}(\text{coef}) / 2$  
    \State $result \gets \text{coef}[2n-1]$  
    \For{$i$ from $2n-2$ \textbf{down to} $0$}  
        \State $result \gets result \times (z - x[i/2]) + \text{coef}[i]$  
    \EndFor  
    \State \Return $result$  
\EndFunction  
\end{algorithmic}  
\end{algorithm} 
% ============================================
\section*{贝塞尔曲线设计}
%% \begin{listing}[H]
%% \caption{Hermite Interpolation Pseudocode}
%% \begin{lstlisting}
%% def HermiteInterpolation(x_, y_, dy_):
%%     if size(x_) != size(y_) or size(x_) != size(dy_):
%%         throw exception("The sizes of x, y, and dy must be equal")
    
%%     n = size(x_)
%%     resize x, y, dy, coef to 2n

%%     for i from 0 to n-1:
%%         x[2*i] = x_[i]
%%         y[2*i] = y_[i]
%%         dy[2*i] = dy_[i]
%%         x[2*i+1] = x_[i]
%%         y[2*i+1] = dy_[i]
%%         dy[2*i+1] = 0

%%     for i from 0 to 2n-1:
%%         coef[i] = y[i]

%%     for level from 1 to 2n-1:
%%         for i from 2n-1 to level:
%%             if i % 2 == 0:
%%                 coef[i] = (coef[i] - coef[i-1]) / (x[i] - x[i-1])
%%             else:
%%                 coef[i] = (coef[i] - coef[i-2]) / (x[i] - x[i-2])
%% \end{lstlisting}
%% \end{listing}
\begin{algorithm}[H]  
\caption{Hermite Interpolation Pseudocode}  
\begin{algorithmic}  
\Function{HermiteInterpolation}{$x\_, y\_, dy\_$}  
    \If{$\text{size}(x\_) \neq \text{size}(y\_)$ or $\text{size}(x\_) \neq \text{size}(dy\_)$}  
        \State \textbf{throw exception}("The sizes of x, y, and dy must be equal")  
    \EndIf  
      
    \State $n \gets \text{size}(x\_)$  
    \State \textbf{resize} $x, y, dy, \text{coef}$ to $2n$  
  
    \For{$i$ \textbf{from} $0$ \textbf{to} $n-1$}  
        \State $x[2*i] \gets x\_[i]$  
        \State $y[2*i] \gets y\_[i]$  
        \State $dy[2*i] \gets dy\_[i]$  
        \State $x[2*i+1] \gets x\_[i]$  
        \State $y[2*i+1] \gets dy\_[i]$  
        \State $dy[2*i+1] \gets 0$  
    \EndFor  
  
    \For{$i$ \textbf{from} $0$ \textbf{to} $2n-1$}  
        \State $\text{coef}[i] \gets y[i]$  
    \EndFor  
  
    \For{$\text{level}$ \textbf{from} $1$ \textbf{to} $2n-1$}  
        \For{$i$ \textbf{from} $2n-1$ \textbf{to} $\text{level}$}  
            \If{$i \mod 2 == 0$}  
                \State $\text{coef}[i] \gets (\text{coef}[i] - \text{coef}[i-1]) / (x[i] - x[i-1])$  
            \Else  
                \State $\text{coef}[i] \gets (\text{coef}[i] - \text{coef}[i-2]) / (x[i] - x[i-2])$  
            \EndIf  
        \EndFor  
    \EndFor  
\EndFunction  
\end{algorithmic}  
\end{algorithm}  

% ============================================
\section*{B.}
通过牛顿插值来估计函数\(f(x) = \frac{1}{1+x^2}\)并作图来观察Runge现象。
\begin{figure}[H]  
    \centering  
    \includegraphics[width=0.5\textwidth]{./image/B.png}  
    \caption{B}
\end{figure}  

% ============================================
\section*{C.}
用切比雪夫多项式来做插值节点可以用牛顿插值多项式一致地逼近目标函数。
\begin{figure}[H]  
    \centering  
    \includegraphics[width=0.5\textwidth]{./image/C.png}  
    \caption{C}
\end{figure}  


% ============================================
\section*{D.}
用hermite插值来实现给定初值节点和节点一阶导数的多项式。 \\
用插值多项式来估计未知时间节点的位置，并用割线斜率来近似速度（即导数斜率）。\\
运行结果如下：
\begin{verbatim}  
distant at 10 is 742.503
over speed at 5.9 with speed 81.0434
\end{verbatim}  


% ===============================================
\section*{E.}
用牛顿插值多项式来估计数据的走向
结果如下：
\begin{figure}[H]  
    \centering  
    \includegraphics[width=0.5\textwidth]{./image/E.png}  
    \caption{E}
\end{figure}  
但是根据实际情况我们知道这个曲线并不符合真实现象，表明了差值可能并不适合用于预测，应考虑最小二乘之类的方法来进行预测。
% ===============================================

\section*{F.}
参数化心形曲线，并用分段三次贝塞尔曲线来逼近目标曲线.
在$bezier\_curve.hpp$中实现$Bezier_curves$函数，接受两个端点的坐标和导数为输入，输出满足书本算法中的一段贝塞尔曲线。
在获取端点导数时做了一点调整\(\gamma(t) \to \frac{1}{s}\gamma(t)\),其中s是两个端点的距离，避免导数值过大生成的贝塞尔曲线自交。

\begin{figure}[H]  
    \centering  
    \includegraphics[width=0.5\textwidth]{./image/plot1.png}  
    \includegraphics[width=0.5\textwidth]{./image/plot2.png}  
    \includegraphics[width=0.5\textwidth]{./image/plot3.png}  
    \caption{F}
\end{figure}  

\end{document}
